
%   File   : LISTUT.PL
%   Author : Bob Welham, Lawrence Byrd, and R.A.O'Keefe
%   Converted to NIP: K Johnson, 11.8.87
%   Updated: 12 February 1985
%   Purpose: list processing utilities

%   I am not sure how much of the original code was by Bob Welham
%   and how much by Lawrence Byrd.  The layout and comments are by
%   R.A.O'Keefe, as are nth*, same_length, shorter_list, and subseq*.
%   Keys_and_values has moved to PROJEC.PL.

:- module(listut).			% SEPIA header

:-comment(categories, ["Data Structures"]).
:- comment(summary, "List processing utilities").
:- comment(author, "Bob Welham, Lawrence Byrd, R.A.O'Keefe, Joachim Schimpf").
:- comment(copyright, 'This file is in the public domain').
:- comment(date, "$Date: 2009/02/19 06:26:40 $").

:- export
	append/3,			%   List x List -> List
	correspond/4,			%   Elem <- List x List -> Elem
	delete/3,			%   List x Elem -> List
	last/2,				%   List -> Elem
	nextto/3,			%   Elem, Elem <- List
	nmember/3,			%   Elem <- Set -> Integer
	nmembers/3,			%   List x Set -> Set
	nth0/3,				%   Integer x List -> Elem
	nth0/4,				%   Integer x List -> Elem x List
	nth1/3,				%   Integer x List -> Elem
	nth1/4,				%   Integer x List -> Elem x List
	numlist/3,			%   Integer x Integer -> List
	perm/2,				%   List -> List
	perm2/4,			%   Elem x Elem -> Elem x Elem
	remove_dups/2,			%   List -> Set
	rev/2,				%   List -> List
	reverse/2,			%   List -> List
	same_length/2,			%   List x List ->
	select/4,			%   Elem x List x Elem -> List
	shorter_list/2,			%   List x List ->
	subseq/3,			%   List -> List x List
	subseq0/2,			%   List -> List
	subseq1/2,			%   List -> List
	sumlist/2.			%   List -> Integer

:- local select/3.

:- mode
	append(?, ?, ?),
	correspond(?, +, +, ?),
	delete(+, +, -),
	last(?, ?),
	nextto(?, ?, ?),
	nmember(?, +, ?),
	nmembers(+, +, -),
	nth0(?, ?, ?),
	nth0(?, ?, ?, ?),
	nth1(?, ?, ?),
	nth1(?, ?, ?, ?),
	numlist(+, +, ?),
	perm(?, ?),
	perm2(?,?, ?,?),
	remove_dups(+, ?),
	rev(?, ?),
	reverse(?, ?),
	reverse(?, +, ?),
	same_length(?, ?),
	select(?, ?, ?, ?),
	shorter_list(?, +),
	subseq(?, ?, ?),
	subseq0(+, ?),
	subseq1(+, ?),
	sumlist(+, ?),
	sumlist(+, +, ?).


%   append(Prefix, Suffix, Combined)
%   is true when all three arguments are lists, and the members of Combined
%   are the members of Prefix followed by the members of Suffix.  It may be
%   used to form Combined from a given Prefix and Suffix, or to take a given
%   Combined apart.  E.g. we could define member/2 (from SetUtl.Pl) as
%	member(X, L) :- append(_, [X|_], L).

append([], L, L).
append([H|T], L, [H|R]) :-
	append(T, L, R).



%   correspond(X, Xlist, Ylist, Y)
%   is true when Xlist and Ylist are lists, X is an element of Xlist, Y is
%   an element of Ylist, and X and Y are in similar places in their lists.

correspond(X, [X|_], [Y|_], Y) :- !.
correspond(X, [_|T], [_|U], Y) :-
	correspond(X, T, U, Y).

%   delete(List, Elem, Residue)
%   is true when List is a list, in which Elem may or may not occur, and
%   Residue is a copy of List with all elements equal to Elem deleted.

delete([], _, []) :- !.
delete([Kill|Tail], Kill, Rest) :- !,
	delete(Tail, Kill, Rest).

	delete([Head|Tail], Kill, [Head|Rest]) :- !,
		delete(Tail, Kill, Rest).

%   last(Last, List)
%   is true when List is a List and Last is its last element.  This could
%   be defined as last(X,L) :- append(_, [X], L).

last(Last, [Last]) :- !.
last(Last, [_|List]) :-
	last(Last, List).

%   nextto(X, Y, List)
%   is true when X and Y appear side-by-side in List.  It could be written as
%	nextto(X, Y, List) :- append(_, [X,Y], List).
%   It may be used to enumerate successive pairs from the list.

nextto(X,Y, [X,Y|_]).
nextto(X,Y, [_|List]) :-
	nextto(X,Y, List).

%   nmember(Elem, List, Index) Possible Calling Sequences
%   nmember(+,+,-) or nmember(-,+,+) or nmember(-,+,-).
%   True when Elem is the Indexth member of List.
%   It may be used to select a particular element, or to find where some
%   given element occurs, or to enumerate the elements and indices togther.

nmember(Elem, [Elem|_], 1).
nmember(Elem, [_|List], N) :-
	nmember(Elem, List, M),
	N is M+1.

% nmembers(+Indices, +Answers, -Ans) or nmembers(-Indices, +Answers, +Ans)
% (But not nmembers(-,+,-), it loops.)
% Like nmember/3 except that it looks for a list of arguments in a list
% of positions.
% eg.   nmembers([3,5,1], [a,b,c,d,e,f,g,h], [c,e,a]) is true 

nmembers([], _, []).
nmembers([N|Rest], Answers, [Ans|RestAns]) :-
	nmember(Ans, Answers, N),
	nmembers(Rest, Answers, RestAns).

%   nth0(?N, ?List, ?Elem) is true when Elem is the Nth member of List,
%   counting the first as element 0.  (That is, throw away the first
%   N elements and unify Elem with the next.)
%   nth1(?N, ?List, ?Elem) is the same as nth0, except that it counts from
%   1, that is nth(1, [H|_], H).

:- comment(nth0/3, [
    amode:(nth0(+,+,-) is det),
    amode:(nth0(-,+,-) is nondet),
    amode:(nth0(-,-,-) is nondet),
    args:["I":"Integer position index, counting from 0",
    	"List":"A list",
	"Elem":"Any term"],
    summary:"Access nth element of a list",
    see_also:[nth1/3,nth0/4,nth1/4],
    desc:html("\
	Succeeds when Elem is the Nth member of List, counting the
	first as element 0.  (That is, throw away the first N elements
	and unify Elem with the next.)
    ")]).

nth0(I, Xs, X) :-
	var(I), 
	nth_nd(I, Xs, X, 0).
nth0(I, Xs, X) :-
	nonvar(I), 
	nth0_det(I, Xs, X).

    nth0_det(0, [X|_], El) :- !, El=X.
    nth0_det(I, [_|Xs], El) :-
	succ(I1, I),
	nth0_det(I1, Xs, El).


:- comment(nth1/3, [
    amode:(nth1(+,+,-) is det),
    amode:(nth1(-,+,-) is nondet),
    amode:(nth1(-,-,-) is nondet),
    args:["I":"Integer position index, counting from 1",
    	"List":"A list",
	"Elem":"Any term"],
    summary:"Access nth element of a list",
    see_also:[nth0/3,nth0/4,nth1/4],
    desc:html("\
	Succeeds when Elem is the Nth member of List, counting the
	first as element 1.
    ")]).

nth1(I, Xs, X) :-
	var(I), 
	nth_nd(I, Xs, X, 1).
nth1(I, Xs, X) :-
	nonvar(I), 
	nth1_det(I, Xs, X).

    nth1_det(1, [X|_], El) :- !, El=X.
    nth1_det(I, [_|Xs], El) :-
	succ(I1, I),
	nth1_det(I1, Xs, El).

    nth_nd(N, [X|_], X, N).
    nth_nd(N, [_|Xs], El, I) :-
	succ(I, I1),
	nth_nd(N, Xs, El, I1).


%   nth0(?N, ?List, ?Elem, ?Rest) unifies Elem with the Nth element of List,
%   counting from 0, and Rest with the other elements.  It can be used
%   to select the Nth element of List (yielding Elem and Rest), or to 
%   insert Elem after the Nth (counting from 1) element of Rest, when
%   it yields List, e.g. nth0(2, List, c, [a,b,d,e]) unifies List with
%   [a,b,c,d,e].  nth1 is the same except that it counts from 1.  nth1
%   can be used to insert Elem before the Nth element (couting from 1) of Rest.

:- comment(nth0/4, [
    amode:(nth0(+,+,-,-) is det),
    amode:(nth0(-,+,-,-) is nondet),
    amode:(nth0(-,-,-,-) is nondet),
    args:["I":"Integer position index, counting from 0",
    	"List":"A list",
	"Elem":"Any term",
	"Rest":"A list"],
    summary:"Access nth element and remainder of a list",
    see_also:[nth0/3,nth1/3,nth1/4],
    desc:html("\
	Unifies Elem with the Nth element of List, counting from 0,
	and Rest with the other elements.  It can be used to select
	the Nth (counting from 0) element of List (yielding Elem and
	Rest), or to insert Elem after the Nth (counting from 1)
	element of Rest, when it yields List, e.g. nth0(2, List, c,
	[a,b,d,e]) unifies List with [a,b,c,d,e].
    ")]).

nth0(I, Xs, X, Rest) :-
	var(I), 
	nth_nd(I, Xs, X, Rest, 0).
nth0(I, Xs, X, Rest) :-
	nonvar(I), 
	nth0_det(I, Xs, X, Rest).

    nth0_det(0, [X|Xs], El, Rs) :- !, El=X, Rs=Xs.
    nth0_det(I, [X|Xs], El, [X|Rs]) :-
	succ(I1, I),
	nth0_det(I1, Xs, El, Rs).


:- comment(nth1/4, [
    amode:(nth1(+,+,-,-) is det),
    amode:(nth1(-,+,-,-) is nondet),
    amode:(nth1(-,-,-,-) is nondet),
    args:["I":"Integer position index, counting from 1",
    	"List":"A list",
	"Elem":"Any term",
	"Rest":"A list"],
    summary:"Access nth element and remainder of a list",
    see_also:[nth0/3,nth1/3,nth0/4],
    desc:html("\
	Unifies Elem with the Nth element of List, counting from 1,
	and Rest with the other elements.  It can be used to select
	the Nth element of List (yielding Elem and Rest), or to insert
	Elem before the Nth (counting from 1) element of Rest, when it
	yields List, e.g. nth1(3, List, c, [a,b,d,e]) unifies List
	with [a,b,c,d,e].
    ")]).

nth1(I, Xs, X, Rest) :-
	var(I), 
	nth_nd(I, Xs, X, Rest, 1).
nth1(I, Xs, X, Rest) :-
	nonvar(I), 
	nth1_det(I, Xs, X, Rest).

    nth1_det(1, [X|Xs], El, Rs) :- !, El=X, Rs=Xs.
    nth1_det(I, [X|Xs], El, [X|Rs]) :-
	succ(I1, I),
	nth1_det(I1, Xs, El, Rs).

    nth_nd(N, [X|Xs], X, Xs, N).
    nth_nd(N, [X|Xs], El, [X|Rs], I) :-
	succ(I, I1),
	nth_nd(N, Xs, El, Rs, I1).


%   numlist(Lower, Upper, List)
%   is true when List is [Lower, ..., Upper]
%   Note that Lower and Upper must be integers, not expressions, and
%   that if Upper < Lower numlist will FAIL rather than producing an
%   empty list.

numlist(Upper, Upper, [Upper]) :- !.
numlist(Lower, Upper, [Lower|Rest]) :-
	Lower < Upper,
	Next is Lower+1,
	numlist(Next, Upper, Rest).



%   perm(List, Perm)
%   is true when List and Perm are permutations of each other.  Of course,
%   if you just want to test that, the best way is to keysort/2 the two
%   lists and see if the results are the same.  Or you could use list_to_bag
%   (from BagUtl.Pl) to see if they convert to the same bag.  The point of
%   perm is to generate permutations.  The arguments may be either way round,
%   the only effect will be the order in which the permutations are tried.
%   Be careful: this is quite efficient, but the number of permutations of an
%   N-element list is N!, even for a 7-element list that is 5040.

perm([], []).
perm(List, [First|Perm]) :-
	select(First, List, Rest),	%  tries each List element in turn
	perm(Rest, Perm).




%   perm2(A,B, C,D)
%   is true when {A,B} = {C,D}.  It is very useful for writing pattern
%   matchers over commutative operators.  It is used more than perm is.

perm2(X,Y, X,Y).
perm2(X,Y, Y,X).

%   remove_dups(List, Pruned)
%   removes duplicated elements from List.  Beware: if the List has
%   non-ground elements, the result may surprise you.

remove_dups(List, Pruned) :-
	sort(List, Pruned).

%   reverse(List, Reversed)
%   is true when List and Reversed are lists with the same elements
%   but in opposite orders.  rev/2 is a synonym for reverse/2.

rev(List, Reversed) :-
	reverse(List, [], Reversed).

reverse(List, Reversed) :-
	reverse(List, [], Reversed).

reverse([], Reversed, Reversed).
reverse([Head|Tail], Sofar, Reversed) :-
	reverse(Tail, [Head|Sofar], Reversed).


%   same_length(?List1, ?List2)
%   is true when List1 and List2 are both lists and have the same number
%   of elements.  No relation between the values of their elements is
%   implied.
%   Modes same_length(-,+) and same_length(+,-) generate either list given
%   the other; mode same_length(-,-) generates two lists of the same length,
%   in which case the arguments will be bound to lists of length 0, 1, 2, ...

same_length([], []).
same_length([_|List1], [_|List2]) :-
	same_length(List1, List2).

%   select(X, Xlist, Y, Ylist)
% >> NB  This is select/4, not select/3 !!
%   is true when X is the Kth member of Xlist and Y the Kth element of Ylist
%   for some K, and apart from that Xlist and Ylist are the same.  You can
%   use it to replace X by Y or vice versa.

select(X, [X|Tail], Y, [Y|Tail]).
select(X, [Head|Xlist], Y, [Head|Ylist]) :-
	select(X, Xlist, Y, Ylist).

%   shorter_list(Short, Long)
%   is true when Short is a list is strictly shorter than Long.  Long
%   doesn't have to be a proper list provided it is long enough.  This
%   can be used to generate lists shorter than Long, lengths 0, 1, 2...
%   will be tried, but backtracking will terminate with a list that is
%   one element shorter than Long.  It cannot be used to generate lists
%   longer than Short, because it doesn't look at all the elements of the
%   longer list.

shorter_list([], [_|_]).
shorter_list([_|Short], [_|Long]) :-
	shorter_list(Short, Long).
	


%   subseq(Sequence, SubSequence, Complement)
%   is true when SubSequence and Complement are both subsequences of the
%   list Sequence (the order of corresponding elements being preserved)
%   and every element of Sequence which is not in SubSequence is in the
%   Complement and vice versa.  That is,
%   length(Sequence) = length(SubSequence)+length(Complement), e.g.
%   subseq([1,2,3,4], [1,3,4], [2]).  This was written to generate subsets
%   and their complements together, but can also be used to interleave two
%   lists in all possible ways.  Note that if S1 is a subset of S2, it will
%   be generated *before S2 as a SubSequence and *after it as a Complement.

subseq([], [], []).
subseq([Head|Tail], Sbsq, [Head|Cmpl]) :-
	subseq(Tail, Sbsq, Cmpl).
subseq([Head|Tail], [Head|Sbsq], Cmpl) :-
	subseq(Tail, Sbsq, Cmpl).



%   subseq0(Sequence, SubSequence)
%   is true when SubSequence is a subsequence of Sequence, but may
%   be Sequence itself.   Thus subseq0([a,b], [a,b]) is true as well
%   as subseq0([a,b], [a]).

%   subseq1(Sequence, SubSequence)
%   is true when SubSequence is a proper subsequence of Sequence,
%   that is it contains at least one element less.

%   ?- setof(X, subseq0([a,b,c],X), Xs).
%   Xs = [[],[a],[a,b],[a,b,c],[a,c],[b],[b,c],[c]] 
%   ?- bagof(X, subseq0([a,b,c,d],X), Xs).
%   Xs = [[a,b,c,d],[b,c,d],[c,d],[d],[],[c],[b,d],[b],[b,c],[a,c,d],
%	  [a,d],[a],[a,c],[a,b,d],[a,b],[a,b,c]] 

subseq0(List, List).

subseq0(List, Rest) :-
	subseq1(List, Rest).


subseq1([_|Tail], Rest) :-
	subseq0(Tail, Rest).

subseq1([Head|Tail], [Head|Rest]) :-
	subseq1(Tail, Rest).

%   sumlist(Numbers, Total)
%   is true when Numbers is a list of integers, and Total is their sum.

sumlist(Numbers, Total) :-
	sumlist(Numbers, 0, Total).

sumlist([], Total, Total).
sumlist([Head|Tail], Sofar, Total) :-
	Next is Sofar+Head,
	sumlist(Tail, Next, Total).


%   copied from setutl.pl:
%   select(?Element, ?Set, ?Residue)
%   is true when Set is a list, Element occurs in Set, and Residue is
%   everything in Set except Element (things stay in the same order).

select(Element, [Element|Rest], Rest).
select(Element, [Head|Tail], [Head|Rest]) :-
	select(Element, Tail, Rest).


